package org.example.binaryTree;

import java.util.HashMap;
import java.util.HashSet;

/**
 *  o1  o2  的最低公共祖先
 */
public class LowestCommonAncestor {




    public static Node Lca(Node head,Node o1,Node o2) {
        HashMap<Node, Node> fatherMap = new HashMap<>();
        fatherMap.put(head,head);
        process(head,fatherMap);

        HashSet<Node> set1 = new HashSet<>();

        Node cur = o1;
        while (cur != fatherMap.get(cur)) {
            set1.add(cur);
            cur = fatherMap.get(cur);
        }
        set1.add(head);
        Node pre = o2;
        while (pre != fatherMap.get(pre)) {
            while (!set1.contains(pre)) {
                pre = fatherMap.get(pre);
            }
           return pre;
        }
        return head;

    }
    public static void process(Node head,  HashMap<Node, Node> fatherMap) {
        if (head == null) {
            return;
        }
        fatherMap.put(head.left,head);
        fatherMap.put(head.right,head);
        process(head.left,fatherMap);
        process(head.right,fatherMap);
    }



    //一个方法解决

    /**
     * 1.o1是o2的lca  或者 o2是o1的LCA
     * 2.互相都不是，向上才能找到
     *
     *
     *
     * @param head
     * @param o1
     * @param o2
     * @return
     */
    public static Node lowestAncestor(Node head,Node o1,Node o2) {
        if (head == null || head == o1 || head == o2) {
            return head;
        }
        Node left = lowestAncestor(head.left,o1,o2);
        Node right = lowestAncestor(head.right,o1,o2);
        if (left != null && right != null) {
            return head;
        }
        return left != null ? left : right;
    }
}
